package b_sorting_advance.a_merge_sort;

import org.junit.Test;
import utils.ArrayGeneric;
import utils.sorting_helper.SortingHelper;
import utils.sorting_helper.SortingTest;

/**
 * @Author: DeLucia
 * @Description:
 * @Date: 2019/1/22 22:28.
 */
@SuppressWarnings("unchecked")
public class MergeSortBottomUp extends SortingTest {
    /**
     * 归并排序 - 利用迭代 自底向上 排序
     * 平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
     * O(nlogn)	    O(nlogn)	O（n）	    是
     *
     * @param arr
     */
    @Override
    public void sort(ArrayGeneric arr) {
        mergeSortBottomUpAdvance(arr); // 递归归并排序
    }

    /**
     * 2 利用迭代 自底向上 的 递归归并, 对arr[left..right]的范围进行排序
     * 也就是先两两一组排序 然后合并和四四一组 最后分成两部分 合并成一部分
     * 性能比递归的稍差
     * 没有使用数组的索引获取元素 - 因为对数组没有特别的性能优势，反而更适合链表的数据结构
     * 更适合链表数据结构的排序（原址排序）
     * 因为链表结构数据之间是通过引用连接，排序时只需要改变引用的位置，而不需要移动地址
     * 所以链表处理起来要比速度更有效率
     *
     * @param arr
     */
    private void mergeSortBottomUp(ArrayGeneric arr) {
        int len = arr.length();
        for (int sz = 1; sz <= len; sz += sz) { // sz 代表每一轮 归并的数据规模，每次增加一倍，即2， 4， 6， 8
            // 边界问题1： i + sz < n 可以保证merge的数据的mid位置不是最后一个元素
            for (int i = 0; i + sz < len; i += sz + sz) { //i 代表每一组数据的起始下标，每次偏移2*sz
                // 对 arr[i..i+sz-1] 和 arr[i+sz..i+2*sz-1].. 进行归并
                // 边界问题2：  i + sz + sz - 1 也有可能超过最后一个元素的下标len - 1
                merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, len - 1));


                // 单元测试 打印下标 分析合并过程
                System.out.print(i + "---" + (i + sz - 1) + "---" + Math.min(i + sz + sz - 1, len - 1) + "\t\t");
            }
            // 单元测试 打印下标 分析合并过程
            System.out.println(arr);
        }
    }

    @Test
    public void test1() {
        mergeSortBottomUp(getRandomIntegerArray(13, 2, 10));
        // 以16个元素排序为例
        // 第1次合并 0---0---1 2---2---3 4---4---5 6---6---7 8---8---9 10---10---11 12---12---13 14---14---15
        // 第2次合并 0---1---3           4---5---7           8---9---11             12---13---15
        // 第3次合并 0---3---7                               8---11---15
        // 最后一次  0---7---15

    }

    /**
     * 优化1： 对长度等于16的数组改用插入排序
     * 优化2： 如果将要合并的左右两个部分， 左边的最右元素小于右边的最左元素则不需合并（已经有序）
     *
     * @param arr
     */
    private void mergeSortBottomUpAdvance(ArrayGeneric arr) {
        int len = arr.length();
        // 对长度小于等于16的数组先改用插入排序
        for (int i = 0; i < len; i += 16)
            insertionSort(arr, i, Math.min(i + 15, len - 1));

        // 接下来直接归并规模从16开始
        for (int sz = 16; sz <= len; sz += sz) {
            for (int i = 0; i + sz < len; i += sz + sz) {
                // 左右两部分如果可以衔接起来形成有序数组时则跳过归并步骤
                if (arr.get(i + sz - 1).compareTo(arr.get(i + sz)) > 0)
                    merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, len - 1));
            }
        }
    }

    /**
     * 当递归到数组规模小于16的时候
     * 为了提高性能改用插入排序
     *
     * @param arr
     * @param left
     * @param right
     */
    private void insertionSort(ArrayGeneric arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            Comparable e = arr.get(i);
            int j;
            for (j = i; j > left && arr.get(j - 1).compareTo(e) > 0; j--) {
                arr.put(j, arr.get(j - 1));
            }
            arr.put(j, e);
        }
    }

    /**
     * 合并arr[left..mid] 和 arr[mid+1..right]
     * 利用辅助数组aux完成
     *
     * @param arr   待排序数组
     * @param left  待排序数组的起始坐标
     * @param mid   待排序数组的中点坐标
     * @param right 待排序数组的结束坐标
     */
    private void merge(ArrayGeneric arr, int left, int mid, int right) {
        // Auxiliary Space -> aux
        ArrayGeneric aux = new ArrayGeneric(right - left + 1);
        // init aux space
        // 把 arr[left,right]复制到新的空间aux[0..right - left]
        for (int i = left; i <= right; i++) {
            aux.put(i - left, arr.get(i));
        }

        // 开始合并左arr[left..mid]右arr[mid+1..right]
        // 临时数组aux起到辅助运算的作用(作为比较和拷贝的数据源, 数据保持不变)
        // 这里需要三个临时指针, 每次比较后向右移动一个位置
        // 原数组arr的左指针 l 对应 辅助空间aux的左指针 l-left
        // 原数组arr的右指针 r 对应 辅助空间aux的右指针 r-left
        // 原数组arr的当前操作位置 c
        // 当c从arr的左侧遍历到右侧, arr 就排序完成了
        int l = left, r = mid + 1;
        for (int c = left; c <= right; c++) {
            if (l > mid) { // 检查 l 的越界问题
                // 如果 l 越过 中点 说明 左空间都合并完成了 接着合并右空间
                arr.put(c, aux.get(r - left));
                r++;
            } else if (r > right) { // 检查 r 的越界问题
                // 如果 r 越过 right 说明 右空间都合并完成了 接着合并左空间
                arr.put(c, aux.get(l - left));
                l++;
            } else if (aux.get(r - left).compareTo(aux.get(l - left)) > 0) {
                // 如果左指针的元素更小那么就替换到源数组的c位置, 同时左指针右移一位
                // 注意左指针可能越过mid导致越界问题
                arr.put(c, aux.get(l - left));
                l++;
            } else {
                // 如果左指针的元素不比右指针的元素更小那么就将右指针的元素替换到源数组的c位置, 同时右指针右移一位
                // 注意右指针可能越过right导致越界问题
                arr.put(c, aux.get(r - left));
                r++;
            }
            // 如果左右指针都走到边界, 整个大循环也正好结束
        }
    }

    @Test
    public void testingSortMethod() {
        ArrayGeneric<Integer> arr = getRandomIntegerArray(2000000, 0, 9);
//        System.out.println(arr);
        long begin = System.currentTimeMillis();
        sort(arr);
        long end = System.currentTimeMillis();
//        System.out.println(arr);
        assert SortingHelper.testSorted(arr);
        System.out.println(end-begin + "ms");
    }
}
